// =====================================================================================
//
//       Filename:  bst.h
//
//    Description:  Description d'une structure d'arbre binaire automatiquement équilibré,
//					de type AVL-Tree (Adelson-Velskii et Landis, 1962)
//
//        Version:  1.0
//        Created:  14/08/2009 15:16:00
//       Revision:  none
//       Compiler:  g++
//
//         Author:  François Hissel (fh), francois.hissel@m4x.org
//        Company:
//
// =====================================================================================

#ifndef BST_H_INC
#define BST_H_INC

template <class T,bool (*compare)(void *a,void *b)> class BstNode;

/**
 * \brief Classe définissant un arbre binaire équilibré.
 *
 * La classe définit un arbre binaire équilibré. Elle encapsule une classe de type BstNode et permet de s'assurer de la pertinence des requêtes sur cette classe.
 * \tparam T Type des objets contenus dans l'arbre
 * \tparam compare Pointeur sur une fonction qui prend en argument deux pointeurs vers des objets de type T et retourne -1 si le premier est strictement inférieur au second, 1 si le premier est strictement supérieur au second, 0 si les deux sont égaux
 */
template<class T,int (*compare)(void *a,void *b)>
class Bst {
	public:
		/**
		 * \brief Destructeur standard
		 *
		 * Le destructeur libère les ressources mémoire allouées à l'arbre. Il détruit récursivement l'arbre et tous ses noeuds.
		 */
		~Bst() {delete root;}

		/**
		 * \brief Insère un élément dans l'arbre
		 *
		 * La fonction insère l'élément passé en argument dans l'arbre en préservant la structure ordonnée et équilibrée.
		 * \param element Nouvel élément à insérer dans l'arbre, qui est copié à la position appropriée
		 */
		void insert(const T &element);
	protected:
		BstNode *root;	//!< Racine de l'arbre binaire. Le pointeur est nul si l'arbre ne contient aucun élément.
};

/**
 * \brief Structure de noeud d'un arbre binaire équilibré, où chaque noeud est inférieur à son fils droit et supérieur à son fils gauche
 *
 * La classe définit une structure de noeud d'arbre binaire équilibré automatiquement et trié de façon à pouvoir exécuter chaque action élémentaire (tri, insertion, suppression) en temps logarithmique
 * \tparam T Type des objets contenus dans l'arbre
 * \tparam compare Pointeur sur une fonction qui prend en argument deux pointeurs vers des objets de type T et retourne -1 si le premier est strictement inférieur au second, 1 si le premier est strictement supérieur au second, 0 si les deux sont égaux
 */
template<class T,int (*compare)(void *a,void *b)>
class BstNode {
	friend class Bst;
	public:
		/**
		 * \brief Constructeur standard
		 * \param pdata Elément à stocker dans le noeud
		 * \param pleft Fils gauche du noeud à créer
		 * \param pright Fils droit du noeud à créer
		 * \param pparent Parent du noeud à créer
		 */
		BstNode(const T &pdata,BstNode *pleft,BstNode *pright,BstNode *pparent):data(pdata),left(pleft),right(pright),parent(pparent),_depth(-1) {}

		/**
		 * \brief Destructeur standard
		 *
		 * Le destructeur libère les ressources associées au noeud, et notamment la mémoire allouée par les fils droit et gauche.
		 */
		~BstNode();

		/**
		 * \brief Retourne la profondeur de l'arbre
		 *
		 * La fonction retourne la profondeur de l'arbre. Si celle-ci a déjà été calculée et stockée dans la variable depth, elle est retournée directement. Sinon, elle est calculée à partir de celle des enfants.
		 */
		int depth();
	protected:
		T data;	//!< Valeur contenue dans le noeud courant
		BstNode<T,compare> *left;	//!< Fils gauche du noeud courant
		BstNode<T,compare> *right;	//!< Fils droit du noeud courant
		BstNode<T,compare> *parent;	//!< Parent du noeud courant, 0 si le noeud est à la racine de l'arbre

		/**
		 * \brief Recherche un élément dans l'arbre
		 *
		 * La fonction recherche l'élément passé en argument et retourne dans l'argument element un pointeur vers la feuille qui le contient. Si l'élément n'est pas trouvé, la fonction retourne faux et element contient la feuille de l'arbre où s'est terminée la recherche. Sa complexité est de O(log n).
		 * \param source Elément à rechercher dans l'arbre
		 * \param element Pointeur vers l'élément recherché s'il est trouvé ou à défaut vers la feuille où s'est terminée la recherche
		 * \return Vrai si l'élément a été trouvé, faux sinon
		 */
		bool search(const T &source,const BstNode<T,compare> *const &element) const;
	private:
		int _depth;	//!< Profondeur du sous-arbre issu du noeud courant. La profondeur est nulle si le sous-arbre est une feuille. Sinon elle est égale à la profondeur maximale des deux sous-arbres issus des fils gauche et droit augmentée de un.
};

#include	"bst.cpp"

#endif /* HEAP_H_ */
